/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
	rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	RC rc;

	// open the page file
	rc = pf.open(indexname, mode);
	if (rc < 0)
		return rc;

	// Check if the page file already has an index in place
	char page[PageFile::PAGE_SIZE];
	rc = pf.read(0, page);
	
	if (rc == RC_INVALID_PID)
		return 0;
		// the first entry in the page file will information for the index
		// variable: rootPid and treeHeight
	else if (rc < 0)
		return rc;
	else
	{
		char cRootPid[4];
		strncpy(cRootPid, page, 4);
		rootPid = atoi(cRootPid);
		
		char cTreeHeight[4];
		strncpy(cTreeHeight, &page[4], 4);
		treeHeight = atoi(cTreeHeight);
		
		return 0;
	}
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	char page[PageFile::PAGE_SIZE];
	memset(page, 0, PageFile::PAGE_SIZE);
	
	char cRootPid[4];
	sprintf(cRootPid, "%04d", rootPid);
	char cTreeHeight[4];
	sprintf(cTreeHeight, "%04d", treeHeight);
	
	strncpy(page, cRootPid, 4);
	strncpy(&page[4], cTreeHeight, 4);

	pf.write(0, page);
	
	return pf.close();
	
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	RC rc;
	
	// if there is no root node, then create a leaf node as the root
	if (treeHeight == 0)
	{
		rootPid = 1;
		BTLeafNode rootNode;
		rc = rootNode.insert(key, rid);
		if (rc < 0)
			return rc;
		
		rootNode.write(rootPid, pf);
		treeHeight = 1;
		return 0;
	}
		
	//
	// First find where it should be through locate. Then insert there.
	//
	IndexCursor fndLeafIndex;
	rc = locate(key, fndLeafIndex);
	if (rc < 0)
		return rc;

	// If found, read in the found leaf node using the index cursor
	BTLeafNode fndLeafNode;
	fndLeafNode.read(fndLeafIndex.pid, pf);

	// Try to insert into the found leaf node
	rc = fndLeafNode.insert(key, rid);

	// If the found leaf node is full, insert and split the node
	if (rc == RC_NODE_FULL)
	{
		BTLeafNode sibLeafNode;
		int parentKey;
		rc = fndLeafNode.insertAndSplit(key, rid, sibLeafNode, parentKey);
		if (rc < 0)
			return rc;

		fndLeafNode.write(fndLeafIndex.pid, pf);
		
		PageId sibNodePid = pf.endPid();
		sibLeafNode.write(sibNodePid, pf);
		
		fndLeafNode.setNextNodePtr(sibNodePid);

		// If the found leaf node is the root 
		if (fndLeafIndex.pid == rootPid)
		{
			BTNonLeafNode parentNonLeafNode;
			parentNonLeafNode.initializeRoot(fndLeafIndex.pid, parentKey, sibNodePid);
			rootPid = sibNodePid+1;
			treeHeight = 2;
			return 0;
		}
		/*else
		{
			BTNonLeafNode parentNonLeafNode;
			parentNonLeafNode.read( some pid , pf);
			rc = parentNonLeafNode.insert(parentKey, sibNodePid);
			if (rc < 0)
				return rc;
		}*/
	}
	else if (rc < 0)
		return rc;
	else
	{
		fndLeafNode.write(fndLeafIndex.pid, pf);
		return 0;
	}
}
					//					2				1				1
RC BTreeIndex::locateRecursion(int searchKey, PageId currPid, int currHeight, IndexCursor& fndCursor)
{
	RC rc;

	// End-case: Finally reach the leaf level
	if (currHeight == treeHeight)
	{
		// Initialize the leaf node
		BTLeafNode fndLeafNode;
		rc = fndLeafNode.read(currPid, pf);
		if (rc < 0)
			return rc;
		rc = fndLeafNode.locate(searchKey, fndCursor.eid);
		if (rc < 0)
			return rc;
		fndCursor.pid = currPid;
		
		return 0;
	}

	// If still at the non leaf node levels
	// Initialize the non leaf node
	BTNonLeafNode fndNonLeafNode;
	fndNonLeafNode.read(currPid, pf);
	
	PageId nextPid;
	rc = fndNonLeafNode.locateChildPtr(searchKey, nextPid);
	if (rc < 0)
		return rc;
	
	return locateRecursion(searchKey, nextPid, currHeight+1, fndCursor);
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	RC rc;
	
	// start at the root node which is at level 1
	rc = locateRecursion(searchKey, rootPid, 1, cursor);
	if (rc < 0)
		return rc;
	
	return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	return 0;
}
